'''
啊这好难，还是做不出来，继续参考大佬题解
'''

# https://blog.csdn.net/m0_52501209/article/details/124144435?ops_request_misc=&request_id=&biz_id=102&utm_term=%E6%9C%80%E9%95%BF%E4%B8%8D%E4%B8%8B%E9%99%8D%E5%AD%90%E5%BA%8F%E5%88%97python&utm_medium=distribute.pc_search_result.none-task-blog-2~all~sobaiduweb~default-1-124144435.nonecase&spm=1018.2226.3001.4187
# author_=王晨刚
# data；2020/4/13
def LAS(a):
    n = len(a)  # 表c存放公共子序列的长度，b存放后续的位置，长度为n
    c = [0 for i in range(n)]  # n个0
    b = [-1 for i in range(n)]  # n个-1
    c[n - 1] = 1  # 最后一个字符的LAS长度
    for i in range(n - 1, -1, -1):  # 倒序从n-1 到0
        maxj = 0
        for j in range(i + 1, n):  # j=i+1~n-1
            if a[i] < a[j] and c[j] > c[maxj]:
                maxj = j  # 刷新maxj
                b[i] = maxj  # 记录i的后继
                # 取得从c[i]的长度
                c[i] = c[maxj] + 1
    return c, b


A = [3, 18, 7, 14, 10, 12, 23, 41, 16, 24]
c, b = LAS(A)
print(c)
print(b)

res = []


def printLAS(b, A, i):
    res.append(A[i])
    while b[i] > 0:
        i = b[i]
        res.append(A[i])
    print(res)


printLAS(b, A, 0)
